Á¤º¸Ã³¸®ÇÐȸ ³í¹®Áö C
Current Result Document :
ÇѱÛÁ¦¸ñ(Korean Title) |
Æò±Õ Áö¿¬ ½Ã°£°ú Æ®·¡ÇÈ ¿ë·®ÀÌ Á¦ÇѵǴ ½ºÆÐ´× Æ®¸® ¹®Á¦ÀÇ 2´Ü°è ÈÞ¸®½ºÆ½ ¾Ë°í¸®Áò |
¿µ¹®Á¦¸ñ(English Title) |
Two Phase Heuristic Algorithm for Mean Delay constrained Capacitated Minimum Spanning Tree Problem |
ÀúÀÚ(Author) |
ÀÌ¿ëÁø
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 10-C NO. 03 PP. 0367 ~ 0376 (2003. 06) |
Çѱ۳»¿ë (Korean Abstract) |
º» ¿¬±¸´Â ·ÎÄà ³×Æ®¿öÅ©ÀÇ ÅäÆú·ÎÁö¸¦ ¼³°èÇϰųª ·çÆ® ³ëµå·ÎºÎÅÍ ¿©·¯ °³ÀÇ Åë½Å °æ·Î¸¦ ±¸ÇÏ´Â µ¥ »ç¿ëµÉ ¼ö ÀÖ´Â DCMST(Delay constrained Capacitated Minimum Spanning Tree) ¹®Á¦¸¦ ´Ù·é´Ù. ±âÁ¸ÀÇ CMST ¹®Á¦´Â ·çÆ® ³ëµåÀÇ ÇÑ Æ÷Æ®°¡ ´ã´çÇÏ´Â Æ®·¡ÇÈÀÇ ¿ë·®¿¡¸¸ Á¦ÇÑÀÌ ÀÖ´Â µ¥ ºñÇØ DCMST ¹®Á¦¿¡´Â ³×Æ®¿öÅ© Æò±Õ Áö¿¬ ½Ã°£ÀÇ Á¦¾à Á¶°ÇÀÌ Ãß°¡µÈ´Ù. ÀÌ ¹®Á¦´Â Á¾´Ü ³ëµåÀÇ Æ®·¡ÇÈ ¿ä±¸·®°ú ³×Æ®¿öÅ©ÀÇ Æò±Õ Áö¿¬ ½Ã°£À» ¸¸Á·½ÃÅ°´Â ½ºÆÐ´× Æ®¸®ÀÇ ÁýÇÕÀ» ±¸ÇÏ´Â °ÍÀ¸·Î ¸ñÀû ÇÔ¼ö´Â Àüü ¸µÅ© ºñ¿ëÀ» ÃÖ¼Ò·Î ÇÏ´Â °ÍÀÌ´Ù. º» ¿¬±¸¿¡¼´Â Æ®·¹À̵å-¿ÀÇÁ¿¡ ±âÁØÇÑ ³ëµå ±³È¯ ¾Ë°í¸®Áò°ú ³ëµå À̵¿ ¾Ë°í¸®Áò ±×¸®°í Æò±Õ Áö¿¬ ¾Ë°í¸®ÁòÀ¸·Î ±¸¼ºµÇ´Â 2 ´Ü°è ÈÞ¸®½ºÆ½À» Á¦½ÃÇÑ´Ù. ½ÇÁ¦ °è»ê °æÇè°ú ¼º´É ºÐ¼®À» ÅëÇØ Á¦¾ÈÇÑ ¾Ë°í¸®ÁòÀÌ Æò±Õ Áö¿¬À» °í·ÁÇÑ ±âÁ¸ÀÇ CMST ¾Ë°í¸®Áòº¸´Ù ºñ¿ë Ãø¸é¿¡ ÀÖ¾î ´õ ¿ì¼öÇÑ Çظ¦ »ý¼ºÇÒ ¼ö ÀÖÀ½À» º¸¿´´Ù. |
¿µ¹®³»¿ë (English Abstract) |
This study deals with the DCMST (Delay constrained Capacitated Minimum Spanning Tree) problem applied in the topological design of local networks or finding several communication paths from root node. While the traditional CMST problem has only the traffic capacity constraint served by a port of root node, the DCMST problem has the additional mean delay constraint of network. The DCMST problem consists of finding a set of spanning trees to link end-nodes to the root node satisfying the traffic requirements at end-nodes and the required mean delay of network. The objective function of problem is to minimize the total link cost. This paper presents two-phased heuristic algorithm, which consists of node exchange, and node shift algorithm based on the trade-off criterions, and mean delay algorithm. Actual computational experience and performance analysis show that the proposed algorithm can produce better solution than the existing algorithm for the CMST problem to consider the mean delay constraint in terms of cost. |
Å°¿öµå(Keyword) |
ÅäÆú·ÎÁö ¼³°è
Topological Design
CMST
Capacitated Minimum Spanning Tree
DCMST
Delay Constrained Capacitated Minimum Spanning Tre
ÈÞ¸®½ºÆ½ ¾Ë°í¸®Áò
Heuristic Algorithm
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|